using namespace std;
#include<iostream>
#include<stack>
#include<vector>

class Solution {
public:
    int calculate(string s) {
        int n = s.size();
        vector<int> st;
        int i = 0;
        char op = '+';
        while (i < n)
        {
            if (s[i] == ' ') i++;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + (s[i++] - '0');
                }

                if (op == '-')
                    st.push_back(0 - tmp);
                else if (op == '+')
                    st.push_back(tmp);
                else if (op == '*')
                    st.back() *= tmp;
                else if (op == '/')
                    st.back() /= tmp;

            }
            else
            {
                op = s[i++];
            }
        }

        int ret = 0;
        for (auto e : st) ret += e;
        return ret;

    }
};





class Solution {
public:
    string decodeString(string s) {
        int n = s.size();
        stack<int> nums;
        stack<string> strs;
        strs.push("");
        int i = 0;
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                nums.push(tmp);
            }

            else if (s[i] == '[')
            {
                i++;
                string tmp;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                strs.push(tmp);
            }

            else if (s[i] == ']')
            {
                int k = nums.top();
                nums.pop();

                string tmp = strs.top();
                strs.pop();

                while (k--)
                {
                    strs.top() += tmp;
                }

                i++;
            }

            else
            {
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    strs.top() += s[i++];
                }
            }

        }

        return strs.top();

    }
};





class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0;
        for (auto x : pushed)
        {
            st.push(x);
            while (st.size() && st.top() == popped[i])
            {
                st.pop();
                i++;
            }
        }

        return i == popped.size();

    }
};